package main

import "fmt"

func main() {
	obstacleGrid := [][]int{{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}
	//obstacleGrid := [][]int{{0, 1}}
	fmt.Println(uniquePathsWithObstacles1(obstacleGrid))
	fmt.Println(uniquePathsWithObstacles1([][]int{{0}}))
}

func uniquePathsWithObstacles(obstacleGrid [][]int) int {
	result := make([]int, len(obstacleGrid[0])+1)
	result[0] = 0
	result[1] = 1
	for col := 0; col < len(obstacleGrid); col++ {
		for row := 1; row <= len(obstacleGrid[0]); row++ {
			if obstacleGrid[col][row-1] == 1 {
				result[row] = 0
				continue
			}
			result[row] = result[row] + result[row-1]
		}
	}
	return result[len(obstacleGrid[0])]
}

func uniquePathsWithObstacles1(obstacleGrid [][]int) int {
	if obstacleGrid[0][0] == 1 {
		return 0
	}
	backStepValue := 1
	for i := 1; i < len(obstacleGrid); i++ {
		if obstacleGrid[i][0] == 1 {
			backStepValue = 0
		}
		obstacleGrid[i][0] = backStepValue
	}
	backStepValue = 1
	for j := 0; j < len(obstacleGrid[0]); j++ {
		if obstacleGrid[0][j] == 1 {
			backStepValue = 0
		}
		obstacleGrid[0][j] = backStepValue
	}
	for i := 1; i < len(obstacleGrid); i++ {
		for j := 1; j < len(obstacleGrid[0]); j++ {
			if obstacleGrid[i][j] == 1 {
				obstacleGrid[i][j] = 0
			} else {
				obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1]
			}

		}
	}
	return obstacleGrid[len(obstacleGrid)-1][len(obstacleGrid[0])-1]
}
